package twobranchTree.connectright;
/**
 * @Date 2020/03/03
 * @author 王光浩
 * @Thinking 使用Morris遍历法+方法一中的方法，使用迭代完成。
 */
public class MyMethodTwo {
	public Node connect(Node node) {
		Node root=node;
		//采用Morris方法按前序遍历整颗树
		while(root!=null) {
			if(root.left==null) {  //返回该子树的root节点（该节点为叶子节点）
				root=root.right;
			}
			else {
				//判断该节点是否遍历过
				Node tem=root.left;
				while(tem.right!=null && tem.right!=root) {
					tem=tem.right;
				}
				if(tem.right==null) {  //该节点没有遍历过
					tem.right=root;
					//将该树的左右子树相连接
					Node left=root.left;
					Node right=root.right;
					while(left!=null && right!=null) {
						left.next=right;
						left=left.right;
						right=right.left;
					}
					root=root.left;
				}
				else {  //该节点遍历过（左子树已经完全遍历）
					root=root.right;
					tem.right=null;
				}
			}
		}
		return node;
	}
}
